//79
function exist(board, word) {
  function travel(i, j, used) {
    if (used.length === word.length) {
      return true;
    } else {
      const res = [];
      if (
        i > 0 &&
        board[i - 1][j] === word[used.length] &&
        used.every((item) => item[0] !== i - 1 || item[1] !== j)
      ) {
        res.push(travel(i - 1, j, used.concat([[i - 1, j]])));
      }
      if (
        i < board.length - 1 &&
        board[i + 1][j] === word[used.length] &&
        used.every((item) => item[0] !== i + 1 || item[1] !== j)
      ) {
        res.push(travel(i + 1, j, used.concat([[i + 1, j]])));
      }
      if (
        j > 0 &&
        board[i][j - 1] === word[used.length] &&
        used.every((item) => item[0] !== i || item[1] !== j - 1)
      ) {
        res.push(travel(i, j - 1, used.concat([[i, j - 1]])));
      }
      if (
        j < board[0].length - 1 &&
        board[i][j + 1] === word[used.length] &&
        used.every((item) => item[0] !== i || item[1] !== j + 1)
      ) {
        res.push(travel(i, j + 1, used.concat([[i, j + 1]])));
      }
      return res.some((item) => item);
    }
  }
  const result = [];

  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[i].length; j++) {
      if (board[i][j] === word[0]) {
        result.push(travel(i, j, [[i, j]]));
      }
    }
  }
  return result.some((item) => item);
}
console.log(exist([["a", "b"]], "ab"));
console.log(1);

//思路看着好像差不多，但慢10倍？？？
var exist = function (board, word) {
  const h = board.length,
    w = board[0].length;
  const directions = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
  ];
  const visited = new Array(h);
  for (let i = 0; i < visited.length; ++i) {
    visited[i] = new Array(w).fill(false);
  }
  const check = (i, j, s, k) => {
    if (board[i][j] != s.charAt(k)) {
      return false;
    } else if (k == s.length - 1) {
      return true;
    }
    visited[i][j] = true;
    let result = false;
    for (const [dx, dy] of directions) {
      let newi = i + dx,
        newj = j + dy;
      if (newi >= 0 && newi < h && newj >= 0 && newj < w) {
        if (!visited[newi][newj]) {
          const flag = check(newi, newj, s, k + 1);
          if (flag) {
            result = true;
            break;
          }
        }
      }
    }
    visited[i][j] = false;
    return result;
  };

  for (let i = 0; i < h; i++) {
    for (let j = 0; j < w; j++) {
      const flag = check(i, j, word, 0);
      if (flag) {
        return true;
      }
    }
  }
  return false;
};
